package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: tgy
 * @Date: 1/21/21 10:49 AM
 */
public class _09_最大值减最小值小于等于num的子数组数量 {

    public static int getMaxMinNum(int[] nums, int level) {

        if (nums == null || nums.length == 0 || level < 0) {

            return 0;
        }

        if (level == 0) {

            return nums.length;
        }

        Deque<Integer> maxDeque = new ArrayDeque<>();
        Deque<Integer> minDeque = new ArrayDeque<>();

        int len = nums.length;
        int leftIndex = 0, rightIndex = 0;

        int count = 0;
        boolean flag = false;
        while (leftIndex != len) {

            if (flag) {

                if (maxDeque.getFirst() < leftIndex) {

                    maxDeque.removeFirst();
                }


                if (minDeque.getFirst() < leftIndex) {

                    minDeque.removeFirst();
                }

            }else {

                while (!maxDeque.isEmpty() && nums[maxDeque.getLast()] < nums[rightIndex]) {

                    maxDeque.removeLast();
                }

                maxDeque.addLast(rightIndex);

                while (!minDeque.isEmpty() && nums[minDeque.getLast()] > nums[rightIndex]) {

                    minDeque.removeLast();
                }

                minDeque.addLast(rightIndex);
            }
            boolean tmpFlag = (nums[maxDeque.getFirst()] - nums[minDeque.getFirst()]) <= level;
            if (tmpFlag && rightIndex < len) {

                rightIndex++;
                flag = false;
            }

            if (!tmpFlag || rightIndex == len){

                // 计算以 leftIndex 开头的子序列个数
                count += (rightIndex - leftIndex);
//                System.out.println("start:"+ nums[leftIndex] +" count:" +(rightIndex - leftIndex));
                leftIndex++;
                flag = true;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        //
        int result = getMaxMinNum(new int[]{1,2,3,4,5}, 2);
        System.out.println(result);
    }
}
